package combinationSum4

import "fmt"

// leetcode377 组合总和 4

// 一维DP数组实现完全背包问题，先背包后物品，背包在每次循环里面，进行组合；先物品后背包，物品在循环内，
// 进行排列，这样会导致一个物品在不同位置出现多次，类似于多重背包。

func combinationSum4(nums []int, target int) int {
	dp := make([]int, target+1)
	dp[0] = 1

	for j := 0; j <= target; j++ {
		for i := 0; i < len(nums); i++ {
			if j >= nums[i] {
				dp[j] += dp[j-nums[i]]
			}
		}
	}
	fmt.Println(dp)
	return dp[target]
}
